#include<stdio.h>
#include<malloc.h>
#include<string.h> 
#include<stdlib.h>
// 定义一个名为program的结构体，表示一个程序  
typedef struct program{  
    char name[20];                // 程序名称，字符数组，最大长度为20  
    int running_time;             // 程序运行时间  
    int enter_time;               // 程序进入队列的时间  
    int priority;                 // 程序的优先级  
    int done_time;                // 用于时间片轮转，表示程序完成的时间  
    int copyRunning_time;         // 用于时间片轮转，表示复制的运行时间（可能是为了轮转时恢复用）  
    int start_time;               // 程序的开始时间  
    struct program* next;         // 指向下一个program结构体的指针，用于链表  
} program;  
  
// 定义一个名为programQueue的结构体，表示一个程序队列  
typedef struct programQueue{  
    struct program* firstProg;    // 指向队列中第一个program结构体的指针  
    struct program* LastProg;     // 指向队列中最后一个program结构体的指针（但命名方式可能会误导，因为一般应该命名为lastProg）  
    int size;                     // 队列中元素的数量  
} programQueue;  
  
// 初始化一个programQueue队列  
void Queueinit(programQueue* queue){  
    if(queue==NULL){  
        return ; // 如果传入的队列指针为空，则直接返回  
    }  
    queue->size = 0; // 队列大小为0  
    queue->LastProg = (program*)malloc(sizeof(program)); // 为队列的尾节点分配内存空间  
    // 注意：此处仅为尾节点分配了内存，但没有初始化name字段或设置next为NULL  
    queue->firstProg = queue->LastProg; // 队列的头部和尾部指向同一个节点（这通常表示一个空队列）  
    // 但是，由于此时LastProg的next未设置为NULL，严格来说这不是一个标准的空队列实现  
}  
  
// 打印一个program结构体数组中的enter_time字段  
void print(struct program pro[],int num){  
    for(int i=0;i<num;i++){  
        printf("%d ",pro[i].enter_time); // 打印每个程序的进入时间  
    }  
}  
  
// 打印programQueue队列中的所有程序名称  
void printQueue(programQueue* queue){  
    if(queue == NULL || queue->firstProg == NULL || queue->firstProg->next == NULL){  
        // 如果队列为空或队列的头节点没有下一个节点（即队列为空），则不打印  
        return;  
    }  
    struct program* p=queue->firstProg->next; // 从头节点的下一个节点开始打印（因为头节点可能是空的或未使用的）  
    while(p!=NULL){  
        printf("%s ",p->name); // 打印程序名称  
        p=p->next; // 移动到下一个节点  
    }  
    printf("\n"); // 打印换行符  
}
// 将一个进程加入到进程队列中  
void EnterQueue(programQueue* queue, struct program* pro){  
	// 为新进程分配内存，并将其设置为当前队列的最后一个节点的下一个节点  
	queue->LastProg->next = (program*)malloc(sizeof(program));  
	// 更新LastProg指针，使其指向新添加的节点  
	queue->LastProg = queue->LastProg->next;  
	// 设置新节点的各个属性，与传入的进程pro的属性相同  
	queue->LastProg->enter_time = pro->enter_time;  
	memcpy(queue->LastProg->name, pro->name, sizeof(pro->name)); // 复制名称  
	queue->LastProg->priority = pro->priority;  
	queue->LastProg->running_time = pro->running_time;  
	queue->LastProg->copyRunning_time = pro->copyRunning_time;  
	queue->LastProg->start_time = pro->start_time;  
	// 队列大小加1  
	queue->size++;  
	// 注意：新节点的next指针尚未设置为NULL，但在实践中，通常在创建新节点时直接设置为NULL  
}  
  
// 从队列中取出一个进程（通常是优先级最高或最先到达的，但此函数只是简单地取第一个）  
program* poll(programQueue* queue){  
	// 取出队列的第一个进程（即firstProg的下一个节点）  
	program* temp = queue->firstProg->next;  
	// 如果队列中只有一个进程（即firstProg的下一个节点就是LastProg），则更新LastProg和firstProg为同一个节点  
	if(temp == queue->LastProg){  
		queue->LastProg = queue->firstProg;  
		// 更新队列大小为0（因为队列已空）  
		queue->size--;  
		// 返回取出的进程  
		return temp;  
	}  
	// 否则，更新firstProg的next指针，跳过第一个进程  
	queue->firstProg->next = queue->firstProg->next->next;  
	// 更新队列大小  
	queue->size--;  
	// 返回取出的进程  
	return temp;  
	// 注意：取出的进程temp的next指针应该被设置为NULL，以防止悬挂指针，但在这个函数中并未显式设置  
}  
  
// 输入多个进程信息，并存储到数组中  
void inputProgram(program pro[], int num){  
	for(int i = 0; i < num; i++){  
		program prog; // 定义一个临时变量来存储用户输入的信息  
		printf("请输入第%d个进程的名字，到达时间，服务时间，优先级\n", i + 1);  
		// 输入进程名字  
		scanf("%s", prog.name);  
		// 输入到达时间  
		scanf("%d", &prog.enter_time);  
		// 输入服务时间  
		scanf("%d", &prog.running_time);  
		// 复制服务时间到copyRunning_time（用于时间片轮转）  
		prog.copyRunning_time = prog.running_time;  
		// 输入优先级  
		scanf("%d", &prog.priority);  
		// 将临时变量prog的信息存储到数组pro中  
		pro[i] = prog;  
	}  
}
// 根据进程的进入时间对进程数组进行排序  
void sortWithEnterTime(program pro[], int num){  
	// 使用冒泡排序算法对进程数组进行排序  
	for(int i = 1; i < num; i++){ // 外层循环控制排序的轮数  
		for(int j = 0; j < num - i; j++){ // 内层循环进行相邻元素的比较和交换  
			if(pro[j].enter_time > pro[j + 1].enter_time){  
				// 如果前一个进程的进入时间大于后一个进程的进入时间，则交换它们  
				program temp = pro[j];  
				pro[j] = pro[j + 1];  
				pro[j + 1] = temp;  
			}  
		}  
	}  
}  
  
// 先到先服务（FCFS）调度算法  
void FCFS(program pro[], int num){  
	// 打印表头  
	printf("进程 到达时间  服务时间 开始时间 完成时间 周转时间 带权周转时间\n");  
	  
	// 先根据到达时间对进程进行排序  
	sortWithEnterTime(pro, num);  
	  
	// 创建一个空的进程队列  
	programQueue* queue = (programQueue*)malloc(sizeof(programQueue));  
	Queueinit(queue); // 假设Queueinit是一个初始化队列的函数，但这里并未给出具体实现  
	  
	// 将第一个进程加入队列  
	EnterQueue(queue, &pro[0]);  
	  
	int time = pro[0].enter_time; // 当前时间设置为第一个进程的到达时间  
	int pronum = 1; // 记录当前正在处理的进程编号  
	float sum_T_time = 0, sum_QT_time = 0; // 用于计算平均周转时间和平均带权周转时间  
	  
	// 当队列中还有进程时，循环执行以下操作  
	while(queue->size > 0){  
		// 从队列中取出一个进程  
		program* curpro = poll(queue);  
		  
		// 如果当前时间小于取出进程的到达时间，则更新时间  
		if(time < curpro->enter_time)  
			time = curpro->enter_time;  
		  
		// 计算完成时间和周转时间  
		int done_time = time + curpro->running_time;  
		int T_time = done_time - curpro->enter_time;  
		sum_T_time += T_time; // 累加周转时间  
		  
		// 计算带权周转时间  
		float QT_time = (float)T_time / (curpro->running_time + 0.0);  
		sum_QT_time += QT_time; // 累加带权周转时间  
		  
		// 模拟进程的执行过程，并将到达的进程加入队列  
		for(int tt = time; tt <= done_time && pronum < num; tt++){  
			if(tt >= pro[pronum].enter_time){  
				EnterQueue(queue, &pro[pronum]);  
				pronum++;  
			}  
		}  
		  
		// 打印当前进程的相关信息  
		printf("%s\t%d\t%d\t%d\t%d\t%d\t%.2f\n", curpro->name, curpro->enter_time, curpro->running_time, time, done_time, T_time, QT_time);  
		  
		// 更新当前时间  
		time += curpro->running_time;  
		  
		// 如果队列为空但还有未处理的进程，则将下一个进程加入队列  
		if(queue->size == 0 && pronum < num){  
			EnterQueue(queue, &pro[pronum]);  
			pronum++;  
		}  
	}  
	  
	// 打印平均周转时间和平均带权周转时间  
	printf("平均周转时间为%.2f\t平均带权周转时间为%.2f\n", sum_T_time / (num + 0.0), sum_QT_time / (num + 0.0));  
	  
	// 注意：这里需要释放队列占用的内存，但代码中并未给出相关操作  
}
// 根据进程的运行时间对进程数组进行排序（短作业优先排序）  
// 参数：  
//   program pro[] - 进程数组  
//   int start - 排序开始的索引  
//   int end - 排序结束的索引（不包括此索引对应的元素）  
void sortWithLongth(program pro[], int start, int end){  
	int len = end - start; // 计算需要排序的元素个数  
	if(len == 1) return; // 如果只有一个元素，则无需排序，直接返回  
  
	// 使用冒泡排序算法对数组进行排序  
	for(int i = 1; i < len; i++){ // 外层循环，控制排序的轮数  
		for(int j = start; j < end - i; j++){ // 内层循环，进行相邻元素的比较和交换  
			// 如果前一个进程的运行时间大于后一个进程的运行时间，则交换它们的位置  
			if(pro[j].running_time > pro[j+1].running_time){  
				program temp = pro[j]; // 创建一个临时变量来保存要交换的进程  
				pro[j] = pro[j+1]; // 将后一个进程赋值给前一个进程  
				pro[j+1] = temp; // 将临时变量（即原来的前一个进程）赋值给后一个进程  
			}   
		}  
	}  
}
void SJF(program pro[],int num) {
	printf("进程 到达时间  服务时间 开始时间 完成时间 周转时间 带权周转时间\n");
	sortWithEnterTime(pro,num);
	programQueue* queue = (programQueue*)malloc(sizeof(programQueue));;
	Queueinit(queue);
	EnterQueue(queue,&pro[0]);
	int time = pro[0].enter_time;
	int pronum=1;    //记录当前的进程 
	float sum_T_time = 0,sum_QT_time = 0;
	while(queue->size>0){
		program* curpro = poll(queue);   //从进程队列中取出进程 
		if(time<curpro->enter_time)
			time =  curpro->enter_time;
		int done_time = time+curpro->running_time;
		int T_time = done_time - curpro->enter_time;
		float QT_time = T_time / (curpro->running_time+0.0) ;
		sum_T_time += T_time;
		sum_QT_time += QT_time;
		int pre = pronum;
		for(int tt = time;tt<=done_time&&pronum<num;tt++){    //模拟进程的执行过程 
			if(tt>=pro[pronum].enter_time){ // 统计从此任务开始到结束之间有几个进程到达 
				pronum++;
			}
		}
		sortWithLongth(pro,pre,pronum);//将到达的进程按照服务时间排序
		for(int i=pre;i<pronum;i++){    //将进程链入队列 
			EnterQueue(queue,&pro[i]);
		}
		pre = pronum;
		printf("%s\t%d\t%d\t%d\t%d\t%d\t%.2f\n",curpro->name,curpro->enter_time,curpro->running_time,time,done_time
			,T_time,QT_time);
		time +=  curpro->running_time;
		if(queue->size==0&&pronum<num){   //防止出现前一个进程执行完到下一个进程到达之间无进程进入 
			EnterQueue(queue,&pro[pronum]);
			pronum++; 
		}
	}
	printf("平均周转时间为%.2f\t平均带权周转时间为%.2f\n",sum_T_time/(num+0.0),sum_QT_time/num);
}
// 根据进程的优先级对进程数组中的一部分进行排序  
void sortWithPriority(program pro[], int start, int end){  
    int len = end - start; // 计算要排序的区间长度  
    if(len == 1) return; // 如果只有一个元素，则无需排序，直接返回  
  
    // 使用冒泡排序算法对进程数组中的一部分进行排序  
    for(int i = 1; i < len; i++){  
        for(int j = start; j < end - i; j++){  
            // 比较相邻两个进程的优先级，如果前一个进程的优先级大于后一个，则交换它们  
            if(pro[j].priority > pro[j + 1].priority){  
                program temp = pro[j];  
                pro[j] = pro[j + 1];  
                pro[j + 1] = temp;  
            }  
        }  
    }  
}  
  
// 高优先级优先（HPF）调度算法  
void HPF(program pro[], int num){  
    printf("进程 到达时间  服务时间 开始时间 完成时间 周转时间 带权周转时间\n");  
  
    // 先根据到达时间对进程进行排序  
    sortWithEnterTime(pro, num); // 注意这里应该使用与HPF相关的排序逻辑，但这里假设它已经是按照到达时间排序的  
  
    // 创建一个空的进程队列  
    programQueue* queue = (programQueue*)malloc(sizeof(programQueue));  
    Queueinit(queue); // 假设Queueinit是一个初始化队列的函数  
  
    // 将第一个进程加入队列  
    EnterQueue(queue, &pro[0]);  
  
    int time = pro[0].enter_time; // 当前时间设置为第一个进程的到达时间  
    int pronum = 1; // 记录当前正在处理的进程编号  
    float sum_T_time = 0, sum_QT_time = 0; // 用于计算平均周转时间和平均带权周转时间  
  
    while(queue->size > 0){  
        // 从队列中取出一个进程  
        program* curpro = poll(queue);  
  
        // 如果当前时间小于取出进程的到达时间，则更新时间  
        if(time < curpro->enter_time)  
            time = curpro->enter_time;  
  
        // 计算完成时间和周转时间  
        int done_time = time + curpro->running_time;  
        int T_time = done_time - curpro->enter_time;  
        sum_T_time += T_time; // 累加周转时间  
  
        // 计算带权周转时间  
        float QT_time = (float)T_time / (curpro->running_time + 0.0);  
        sum_QT_time += QT_time; // 累加带权周转时间  
  
        // 记录当前处理的进程编号，以便后续将到达的进程加入队列  
        int pre = pronum;  
  
        // 模拟进程的执行过程，统计从此任务开始到结束之间有几个进程到达  
        for(int tt = time; tt <= done_time && pronum < num; tt++){  
            if(tt >= pro[pronum].enter_time){  
                pronum++; // 如果有进程到达，则增加进程编号  
            }  
        }  
  
        // 将到达的进程按照优先级排序，并加入队列  
        sortWithPriority(pro, pre, pronum); // 注意这里排序后需要更新队列中的顺序  
  
        // 将排序后的进程重新加入队列  
        for(int i = pre; i < pronum; i++){  
            EnterQueue(queue, &pro[i]);  
        }  
  
        // 打印当前进程的相关信息  
        printf("%s\t%d\t%d\t%d\t%d\t%d\t%.2f\n", curpro->name, curpro->enter_time, curpro->running_time, time, done_time, T_time, QT_time);  
  
        // 更新当前时间  
        time += curpro->running_time;  
  
        // 如果队列为空但还有未处理的进程，则将下一个进程加入队列  
        // 注意：此处的逻辑可能需要调整，因为按照HPF算法，应该根据优先级选择下一个执行的进程  
        if(queue->size == 0 && pronum < num){  
            // 这里可能需要根据优先级来选择下一个进程，而不是简单地按照编号  
            // ...  
            // 假设我们直接加入下一个进程到队列  
            EnterQueue(queue, &pro[pronum]);  
            pronum++;  
        }  
    }  
  
    // 打印平均周转时间和平均带权周转时间  
    printf("平均周转时间为%.2f\t平均带权周转时间为%.2f\n",sum_T_time/(num+0.0),sum_QT_time/(num+0.0));
}
// 轮转调度（Round-Robin Scheduling）算法  
void RR(program pro[], int num){  
    printf("请输入时间片大小: "); // 提示用户输入时间片的大小  
    int timeslice;               // 定义变量来存储时间片大小  
    scanf("%d",&timeslice);      // 从标准输入读取用户输入的时间片大小  
  
    printf("进程 到达时间  服务时间 进入时间 完成时间 周转时间 带权周转时间\n");  
  
    // 根据到达时间对进程进行排序  
    sortWithEnterTime(pro, num);  
  
    // 创建一个空的进程队列  
    programQueue* queue = (programQueue*)malloc(sizeof(programQueue));  
    Queueinit(queue); // 初始化队列  
  
    // 假设第一个进程立即开始执行  
    pro[0].start_time = pro[0].enter_time;  
    EnterQueue(queue, &pro[0]); // 将第一个进程加入队列（尽管它已经开始执行）  
  
    int time = 0; // 当前时间，初始化为0  
    int pronum = 1; // 记录当前正在处理的进程编号，初始化为1（因为第一个进程已经处理）  
    float sum_T_time = 0, sum_QT_time = 0; // 用于计算平均周转时间和平均带权周转时间  
  
    // 当队列中还有进程或者还有未处理的进程时，继续循环
	while(queue->size > 0){  
        // 从队列中取出头节点（即当前要执行的进程）  
        program* curpro = poll(queue); // 从队列中取出头节点   
  
        // 如果当前时间小于取出进程的到达时间，则更新时间到该进程的到达时间  
        if(time < curpro->enter_time)  
            time = curpro->enter_time;  
  
        // 判断当前进程是否能在一个时间片内完成  
        if(timeslice >= curpro->running_time){   // 如果剩余时间小于时间片  则此任务完成  
            // 模拟进程执行过程，从当前时间到进程完成时间  
            for(int tt = time; tt <= time + curpro->running_time && pronum < num; tt++){  
                // 统计从当前时间开始到结束之间到达的进程  
                // 注意：这里我们假设进程是按照enter_time顺序排列的  
                if(tt >= pro[pronum].enter_time){  
                    // 如果有新进程到达，则将其加入队列并更新下一个要处理的进程编号  
                    pro[pronum].start_time = tt;  
                    EnterQueue(queue, &pro[pronum]);  
                    pronum++;  
                }  
            }  
  
            // 更新当前时间到进程完成时间  
            time += curpro->running_time;  
            // 标记当前进程已完成  
            curpro->running_time = 0;  
            // 设置完成时间  
            curpro->done_time = time;  
  
            // 计算并累计周转时间和带权周转时间  
            int T_time = curpro->done_time - curpro->start_time;  
            // 注意：这里应该是用服务时间copyRunning_time来计算带权周转时间，但您的代码中使用了copyRunning_time，需要确认是否正确  
            float QT_time = T_time / (curpro->copyRunning_time + 0.0);  
            sum_T_time += T_time;  
            sum_QT_time += QT_time;  
  
            // 打印进程信息  
            printf("%s\t%d\t%d\t%d\t%d\t%d\t%.2f\n", curpro->name, curpro->enter_time, curpro->copyRunning_time,  
                   curpro->start_time, curpro->done_time, T_time, QT_time);  
  
            // 检查是否所有进程都已加入队列（防止在进程间有空隙）  
            if(queue->size == 0 && pronum < num){  
                // 如果队列为空但还有未处理的进程，则将下一个进程加入队列  
                pro[pronum].start_time = pro[pronum].enter_time;  
                EnterQueue(queue, &pro[pronum]);  
                pronum++;  
            }  
  
            // 当前进程已完成，继续下一个循环  
            continue;   
        }  
  
        // 如果进程不能在一个时间片内完成  
        for(int tt = time; tt <= time + timeslice && pronum < num; tt++){  
            // 模拟进程执行过程，只执行一个时间片  
            // 统计从当前时间开始到时间片结束之间到达的进程  
            if(tt >= pro[pronum].enter_time){  
                // 如果有新进程到达，则将其加入队列并更新下一个要处理的进程编号  
                pro[pronum].start_time = tt;  
                EnterQueue(queue, &pro[pronum]);  
                pronum++;  
            }  
        }  
  
        // 更新当前时间  
        time += timeslice;  
        // 更新当前进程的剩余运行时间  
        curpro->running_time -= timeslice;  
  
        // 将当前进程（未完成的）重新加入队列  
        EnterQueue(queue, curpro); //当前程序未完成  继续添加到队列中   
  
        // 同样检查是否所有进程都已加入队列（防止在进程间有空隙）  
        if(queue->size == 0 && pronum < num){  
            // 如果队列为空但还有未处理的进程，则将下一个进程加入队列  
            pro[pronum].start_time = pro[pronum].enter_time;  
            EnterQueue(queue, &pro[pronum]);  
            pronum++;  
        }  
    }  
  
	printf("平均周转时间为%.2f\t平均带权周转时间为%.2f\n\n",sum_T_time/(num+0.0),sum_QT_time/(num+0.0));
} 
void choiceMenu(){
	printf("请选择进程调度算法：\n\n");
	printf("1.先来先服务算法\n2.短进程优先算法\n3.高优先级优先\n4.时间片轮转算法\n5.返回\n6.退出\n"); 
}
// 菜单函数，用于展示和选择进程调度算法  
void menu(){  
	int proNum; // 声明一个整数变量，用于存储用户输入的进程数量  
	  
	// 提示用户输入进程的个数  
	printf("请输入进程的个数：");  
	scanf("%d",&proNum); // 从标准输入读取用户输入的进程数量  
	  
	// 使用变长数组（C99标准）来创建对应数量的进程结构体数组  
	program pro[proNum]; // 声明一个名为pro的变长数组，数组元素类型为program，数量为proNum  
	  
	// 调用inputProgram函数，输入每个进程的信息  
	inputProgram(pro, proNum); // 输入proNum个进程的信息  
	  
	// 调用choiceMenu函数来显示选择菜单（但这里并未给出choiceMenu的实现）  
	choiceMenu();  
	  
	// 使用while循环实现无限菜单循环  
	int choice; // 声明一个整数变量，用于存储用户选择的选项  
	while(1){ // 无限循环  
		// 读取用户选择的选项  
		scanf("%d",&choice);  
		  
		// 使用switch语句根据用户选择执行不同的进程调度算法  
		switch(choice){  
			case 1: // 用户选择1，执行先来先服务（FCFS）算法  
				system("cls"); // 清除控制台（在Windows系统上）  
				FCFS(pro, proNum); // 调用FCFS函数  
				choiceMenu(); // 重新显示选择菜单  
				break;   
			case 2: // 用户选择2，执行短作业优先（SJF）算法  
				system("cls");  
				SJF(pro, proNum);  
				choiceMenu();  
				break;   
			case 3: // 用户选择3，执行高响应比优先（HPF）算法  
				system("cls");  
				HPF(pro, proNum);  
				choiceMenu();  
				break;  
			case 4: // 用户选择4，执行轮转调度（RR）算法  
				system("cls");  
				RR(pro, proNum);  
				choiceMenu();  
				break; 
			case 5:
				 choiceMenu();
				 break;
			case 6: // 用户选择5，退出程序  
				return;  
			default: 
				break;  
		}  
	}  
}  
  
// 主函数，程序的入口点  
int main(){  
	menu(); 
	return 0; 
}